
	
LocalSearch::LocalSearch( const char* input_file ) : Algorithm( input_file ){
	
	Best = initHeuristic();
	quality_best = getSolutionQuality(Best);
}

//ok
int* LocalSearch::initHeuristic(){
	
	int index[L];
	for( int i = 0; i < L; ++i )
		index[i] = i;
	
	for( int i = 0; i < L; ++i )
		swap( &index[i], &index[rand()%L] );
	
	int *init_solution = new int[k];
	for( int i = 0; i < k; ++i )
		init_solution[i] = index[i];
		
	return init_solution;
}

LocalSearch::~LocalSearch(){
	delete [] Best;
}

void LocalSearch::solve(){
	time_t start = time(NULL);
	
	do{
		
		int *neighbor = getNeighbor(Best);
		
		
		int quality_neighbor = getSolutionQuality(neighbor);
		
		if(quality_neighbor > quality_best){
			copySolution(Best, neighbor);
			quality_best = quality_neighbor;
		}
		
		//cout << quality_best << endl;
		delete neighbor;
	}while(time(NULL)-start < 60);
	
}

int* LocalSearch::getNeighbor(int *source_solution){
	int* neighbor = new int[k];
	
	for(int i = 0; i < k; ++i)
		neighbor[i] = source_solution[i];
	
	int set_to_be_inserted;
	bool repeated_value;
	do{
		set_to_be_inserted = rand()%L;
		repeated_value = false;
		for(int i = 0; i < k; ++i){
			if(source_solution[i] == set_to_be_inserted){
				repeated_value = true;
				break;
			}
		}
	}while(repeated_value);
	
	neighbor[rand()%k] = set_to_be_inserted;
	
	return neighbor;
}

int* LocalSearch::getNeighbor2(int *source_solution){
	
	int set_to_be_inserted;
	int set_to_be_removed;
	
	{
		int sum_cardilaties = 0;
		for(int i = 0; i < L; ++i)
			sum_cardilaties += sets[i].cardinality();
		
		float probabilities[L];
		probabilities[0] = (float)sets[0].cardinality()/(float)sum_cardilaties;
		for(int i = 1; i < L; ++i)
			probabilities[i] = 
				(float)sets[i].cardinality()/(float)sum_cardilaties + probabilities[i-1];
		probabilities[L-1] = 1;
		
		bool repeated_value;
		do{
			
			float p = (float)rand()/(float)RAND_MAX;
			for(int i = 0; i < L; ++i){
				if(p <= probabilities[i]){
					set_to_be_inserted = i;
					break;
				}
			}
					
			repeated_value = false;
			for(int i = 0; i < k; ++i){
				if(source_solution[i] == set_to_be_inserted){
					repeated_value = true;
					break;
				}
			}
		}while(repeated_value);
	}
	
	{
		float sum_cardilaties = 0.0;
		for(int i = 0; i < k; ++i)
			sum_cardilaties += 1.0/(float)sets[source_solution[i]].cardinality();
		
		float probabilities[k];
		probabilities[0] = (1.0/(float)sets[source_solution[0]].cardinality())/(float)sum_cardilaties;
		for(int i = 1; i < k; ++i)
			probabilities[i] = 
				(1.0/(float)sets[source_solution[i]].cardinality())/(float)sum_cardilaties + probabilities[i-1];
		probabilities[k-1] = 1;
		
		bool repeated_value;
		
		do{
			float p = (float)rand()/(float)RAND_MAX;
			for(int i = 0; i < k; ++i){
				if(p <= probabilities[i]){
					set_to_be_removed = i;
					break;
				}
			}
			repeated_value = false;
			if(set_to_be_removed == set_to_be_inserted)
				repeated_value = true;
		}while(repeated_value);
	}
	
	int* neighbor = new int[k];
		
	for(int i = 0; i < k; ++i)
		neighbor[i] = source_solution[i];
	
	neighbor[set_to_be_removed] = set_to_be_inserted;
	
	return neighbor;
}

int LocalSearch::getSolutionQuality(int* source_solution){
	
	Set temp;
	temp.union_(&sets[source_solution[0]]);
	
	for( int i = 1; i < k; ++i )
		temp.intersection(&sets[source_solution[i]]);

	return temp.cardinality();
}

void LocalSearch::copySolution(int* s1, int* s2){
	for( int i = 0; i < k; ++i )
		s1[i] = s2[i];
}

void LocalSearch::printSolution(int* s){
	Set temp;
	temp.union_(&sets[s[0]]);
	
	for( int i = 1; i < k; ++i )
		temp.intersection(&sets[s[i]]);
	
	temp.print();
}

int LocalSearch::getQualityOfBest(){
	return quality_best;
}
